% !Mode:: "TeX:UTF-8"
\chapter*{Введение}
\addcontentsline{toc}{chapter}{Введение}

%Мысль первая: Есть тестирование программами, но для него надо
%генерировать программы.
%
%Мысль вторая: Можно писать вручную, использовать готовые программы
%или погенерировать случайно. Но это всё плохо.
%
%Мысль третья: Поэтому надо генерировать по-умному, а именно отделять
%цель тестирования от генерации программы. При этом не забываем, что
%есть куча других методов построения программ, которые не выделяют
%цели тестирования (model checking для достижения особых случаев в
%поведении, coverage-based анализ, генетический сбор программ как
%хромосом и другие)
%
%Мысль четвертая: Показать, что процесс построения через цели
%тестирования является хорошим
%
%Ну и далее речь пойдет уже построении программ для шаблонов

Диссертация посвящена вопросам функционального тестирования
микропроцессоров. Среди всевозможных способов функционального
тестирования своей наглядностью и относительно невысокой
трудоемкостью выделяется тестирование машинными программами. Эти
программы помещаются в память машины, возможно туда же помещается и
некоторая дополнительная информация, затем машина запускается,
микропроцессор считывает инструкции программы одну за другой и
исполняет их. ...Микропроцессор работает в разных ситуациях... После
того, как машина закончила свою работу, на основе анализа ее
состояния и трассы исполнения принимается решение о корректности
работы микропроцессора.

Важным является вопрос качества тестирования --- насколько полно был
протестирован микропроцессор, насколько разнообразными были те
ситуации, в которых работал микропроцессор на использованных
машинных программах. В предельном случае тестирование будет полным,
если количество машинных программ соответствует пространству всех
состояний микропроцессора. Однако это пространство настолько
огромное, что даже построение соответствующих ему программ
невозможно.

До сих пор активно используется ручное написание программ. В
основном это такие <<узкие>> места микропроцессора, о которых
сообщают его разработчики. Другой случай --- это так называемые
<<крайние>> случаи исполнения инструкций.

Однако для более полного тестирования построение машинных программ
автоматизируется. Правда, зачастую эта автоматизация не уходит
дальше случайно сгенерированных программ или переиспользования
программ, которые были подготовлены для совместимых
микропроцессоров. Тем не менее, даже после такого тестирования всё
ещё остаются ошибки и довольно критичные [FDIV].

В ИнстиБыло предложено строить машинные программы (т.е. тесты)
нацеленным образом. Это означает формулирование сначала целей
тестирования, а затем автоматическая генерация тестов,
удовлетворяющих целям тестирования [MicroTESK]. Например, в качестве
цели тестирования может быть выбрана особая ситуация в работе
микропроцессора (скажем, возникновение переполнения), соответственно
эта ситуация должна произойти при исполнении теста.

>>>>> Написать, что эта технология неплохая...

Автоматическое построение тестов, удовлетворяющих целям
тестирования, является сложной задачей с алгоритмической точки
зрения. Но в то же время ее решение необходимо для генерации тестов.
До сих пор эта задача не решена для произвольных целей тестирования.
Всё это определило актуальность задачи и важность ее решения. В том
числе данная статья посвящена задаче автоматического построения
тестов.

Очевидно, что сложность построения тестов напрямую зависит от тех
целей, которые необходимо достичь в тестах. Часто используются
специальные цели, для которых построение тестов выполняется
относительно просто [TSE]. В качестве примера, можно привести цели,
которые состоят из заданной последовательности инструкций с
незаданными аргументами - регистрами или непосредственными
значениями - с указанием зависимостей между аргументами (например,
одна инструкция записывает значение в регистр - другая этот регистр
читает). Однако не все цели тестирования выражаются в такой простой
форме. Примером такой цели может быть возникновение кэш-попадания
при исполнении некоторой инструкции.

Для дальнейшего важными являются следующие моменты. Во-первых, в
микропроцессоре есть подсистемы, которые ведут себя как кэш-память
(собственно, кэш-память в узком понимании этого термина, различные
буферы, хранящие временные данные). Далее такие подсистемы будут
называться кэширующими буферами. Их можно представить как множество
пар "(адрес, данные)", в которых все адреса разные (термин "данные"
понимается в узком смысле, а именно как информация, которая хранится
в оперативной памяти и используется в процессах счета). Обращением к
кэширующему буферу будем называть процедуру получения данных,
хранящихся по заданному адресу. Обращение будет считаться успешным
(эта ситуация называется кэш-попаданием), если в кэширующем буфере
есть пара с заданным адресом. В противном случае обращение будем
считать неуспешным (и называть эту ситуацию кэш-промахом).

Во-вторых, во время исполнения инструкций обращения к памяти могут
происходить обращения к кэширующим буферам. Например, такие
обращения возможны при трансляции адреса, если в микропроцессоре
хранятся последние осуществленные трансляции адресов. Или такие
обращения возможны при работе с данными оперативной памяти,
поскольку микропроцессор хранит те данные, к которым недавно были
обращения.

В-третьих, в качестве целей тестирования будем рассматривать
заданные последовательности кэш-попаданий/кэш-промахов. Тесты,
удовлетворяющие таким целям тестирования, могут использоваться для
тестирования модулей управления памяти (MMU) микропроцессоров.
Кэш-попадания/кэш-промахи происходят (или не происходят) в
зависимости от адреса и состояния кэширующего буфера. Адрес
вычисляется на основе аргументов инструкции. Поэтому зависимые
аргументы инструкций порождают и зависимые адреса. Кроме того,
состояние кэширующего буфера изменяется заданным образом в
зависимости от тех же кэш-попаданий/кэш-промахов. А именно, при
кэш-промахе некоторые данные из кэширующего буфера вытесняются и на
их место помещаются данные по заданному в обращении адресу. Иными
словами, состояния кэширующего буфера в разных инструкциях также
являются зависимыми. Тем самым рассматриваемая цель тестирования
порождает множество зависимостей на значения аргументов инструкций и
состояние микропроцессора.

По сути построение тестов для рассматриваемых целей тестирования
требует решения задачи выполнимости. Задача выполнимости, т.е.
вычисления значений аргументов предиката, на которых он истинен,
является известной сложной задачей.

В-четвертых, вопрос представления решения. Состояние кэширующего
буфера состоит из пар чисел (адрес и данные). Однако не любой
микропроцессор позволяет задать состояние кэширующего буфера
напрямую (заполнением парами чисел). Даже если это и возможно, то
изменение состояний всех нужных кэширующих буферов перед каждым
тестом увеличит время проведения тестирования. Например, увеличение
времени на пару секунд для 100000 тестов увеличит время генерации
тестов более чем на 50 часов. Решением этой проблемы была бы
генерация инициализирующих инструкций. Такие инструкции помещаются
перед тестом и подготавливают микропроцессор к исполнению этого
теста. Другим возможным решением могло бы быть более оптимальное
использованием заданного начального состояния кэширующих буферов,
если о нем имеется информация. В данной статье рассматривается
генерация инициализирующих инструкций.



///// добавки

\section{Модуль управления памятью}

Модуль управления памятью (MMU, Memory Management Unit) ---
логически связанный набор модулей микропроцессора, который выполняет
основные функции обращения к памяти~\cite{MMU}. Практически ни один
микропроцессор не обходится без MMU, причем его организация
становится всё сложнее, а требования к корректности функционирования
-- всё строже.

MMU используется для выполнении инструкций обращения к памяти.
Основными функциями MMU являются:
\begin{enumerate}
  \item \emph{трансляция адресов}: преобразование логических адресов
  в физические;
  \item \emph{организация виртуальной памяти};
  \item \emph{организация защиты} адресного пространства процесса от
  других процессов;
  \item \emph{организация кэширования данных оперативной памяти}
  (иногда эту функцию включают в MMU~\cite{vorobyev},~иногда ---
  нет~\cite{thompson}).
\end{enumerate}

Согласно этим функциям MMU может управлять следующими модулями
микропроцессора:
\begin{itemize}
  \item кэш-память (кэш-память данных и кэш-память инструкций)
  первого уровня, второго уровня (возможно, и третьего уровня);
  \item TLB (Translation Lookaside Buffer) -- буфер, задающий
  соответствие некоторых страниц виртуальной памяти кадрам
  физической памяти;
  \item таблица страниц -- различным образом организованное полное
  соответствие всех страниц виртуальной памяти кадрам физической
  памяти;
  \item сегментные регистры -- содержат адреса начала сегментов;
  \item различные другие буферы.
\end{itemize}

Организация кэширования в MMU отличается от организации кэширования
программных систем (баз данных, операционных систем) тем, что в микропроцессорах
применяется довольно ограниченный набор стратегий вытеснения. Наиболее часто применяются
стратегии вытеснения \LRU, \FIFO и \PseudoLRU. Это связано с особыми требованиями
к эффективности реализации алгоритмов вытеснения в микропроцессорах (вся реализация
алгоритма вытеснения должна располагаться на кристалле и не давать большой проигрыш по времени).
%% тут об этом сказать или чуток попозже?

%\subsection{Виртуальная память}
%
%ссылка на Таненбаума
%
%Виртуальная память --- это механизм, позволяющий
%
%эффективные, виртуальные, логические, физические адреса
%
%виртуальное адресное пространство, сегменты, отображаемые и
%неотображаемые
%
%обработка отсутствия страницы (программно или аппаратно), прерывание
%-- Таненбаум, стр.243
%
%\subsection{Буфер трансляции адресов}
%
%таблицы страниц
%
%быстрый ассоциативный буфер для процессов, один буфер для всех
%процессов
%
%\subsection{Устройства кэш-памяти}
%
%иерархия
%
%стратегия вытеснения
%
%политика кэширования

%\subsection{Модели модуля управления памятью}

Для описания модулей управления памятью применяются различные
\emph{модели}. \emph{Структурные модели} описывают множество
модулей, которыми управляет MMU в данном микропроцессоре.
\emph{Потоковые модели} описывают потоки данных алгоритма получения
физических адресов по виртуальным. В качестве данных используются
битовые поля физических и виртуальных
адресов~\cite{FundamentalOfComputerOrganizationAndDesign}. %Они нам
%пригодятся для понимания того, какие таблицы и буферы является
%подчиненными.
Применение автоматных моделей для описания MMU в литературе не
замечено.

%под моделью понимается набор терминов и отношений на них. У меня
%термины: буферы и таблицы, отношения: подчинение и стрелка. В
%потоковой модели термины: блоки, регистры; отношения: передача
%данных по стрелке.


\section{Методы генерации тестовых программ}

Тестирование микропроцессоров является важной составляющей частью
процесса их разработки. Тестированию может подвергаться как готовая
микросхема, так и ее модель. Тестирование может проводиться как на
модульном, так и на системном уровне. В данной работе речь идет о
системном функциональном тестировании. Иными словами, целью
тестирования является проверка правильности функционирования
микропроцессора целиком. Эта проверка выполняется путем запуска на
микропроцессоре (или его модели) специальных машинных программ
(далее такие программы будут называться \emph{тестовыми}).

Системное функциональное тестирование микропроцессоров включает в
себя следующие этапы~\cite{kamkin}:
\begin{enumerate}
\item определение целей тестирования, тестового покрытия и тестовых
ситуаций (структурные -- какие инструкции включать в тестирование --
и функциональные -- как инструкции должны быть исполнены);
\item генерация тестовых программ для тестовых ситуаций;
\item исполнение тестовых программ на микропроцессоре, получение
выходных данных (трасса исполнения, финальные значения регистров);
\item вынесение вердикта на основе анализа выходных данных.
\end{enumerate}

Данная работа посвящена одному из этапов этого процесса, а именно
генерации тестовых программ. В настоящее время в практике системного
функционального тестирования микропроцессоров можно выделить
следующие подходы к построению тестовых программ:
\begin{itemize}
\item \emph{ручная разработка тестовых программ} хоть и практически неприменима
для полного тестирования микропроцессора, всё же может применяться
для тестирования особых, крайних случаев;
\item \emph{тестирование с использованием кросс-компиляции} применяется часто
из-за невысокой сложности его проведения: после согласования
спецификации микропроцессора можно начинать делать кросс-компилятор,
а код, предназначенный для кросс-компиляции, уже готов. Однако
гарантировать полноту такое тестирование не может;
\item \emph{случайная генерация тестовых программ} применяется так же часто в
силу простоты автоматизации. Сгенерированные таким образом тестовые
программы позволяют быстро обнаружить простые ошибки, однако не
гарантируют полноты тестирования. Разрабатываются и более сложные
варианты случайной генерации~\cite{muGP};
\item \emph{нацеленная генерация тестовых программ} (зачастую, на основе тестовых
шаблонов) предполагает разделение процесса генерации тестовой
программы на два этапа: на первом на основе тестовых ситуаций
подготавливаются тестовые шаблоны -- абстрактные представления
тестовых программ, задающих цели -- а на втором этапе по тестовым
шаблонам генерируются тестовые программы.
\end{itemize}

Нацеленная генерация тестовых программ особенно важна в тех случаях,
когда тестовая программа напрямую не может воздействовать на нужную
для тестирования подсистему (например, системное тестирование
проводится на всем микропроцессоре целиком, а нацелено оно может
быть именно на модуль управления памяти).

Тестовые шаблоны могут описывать следующие свойства тестовых
программ (т.е. это те средства, которыми выражаются цели шаблона,
т.е. на что будет нацелена сгенерированная по нему тестовая
программа):
\begin{itemize}
\item заданная последовательность инструкций (только коды операций или
коды операций с аргументами);
\item заданная последовательность типов инструкций;
\item выборка инструкций заданных типов;
\item аргументы инструкций (регистры, непосредственные
значения, переменные величины);
\item дополнительные ограничения на инструкции;
\item дополнительные ограничения на отдельные аргументы инструкций,
аргументы разных инструкций;
\item дополнительные функциональные ограничения на инструкции (при
исполнении должны произойти некоторые заданные события).
\end{itemize}

\section{Разработка генераторов тестовых программ}

Выделяют следующие подзадачи при генерации тестовых программ по
тестовым шаблонам (подзадачи могут решаться по
отдельности~\cite{kamkin} или итеративно для каждой очередной
выделяемой инструкции~\cite{GenesysPro}):
\begin{enumerate}
  \item выбор последовательности инструкций / выбор очередной
  инструкции;
  \item выбор аргументов (не значений, а имен аргументов!) инструкций /
  выбор аргументов очередной инструкции;
  \item построение программы, инициализирующей микропроцессор для выполнения
  инструкций тестового шаблона (или построение \emph{инициализирующей программы}).
\end{enumerate}

Решение этих задач составляет основу генераторов тестовых программ.
Настоящая работа посвящена исследованию методов построения
инициализирующих программ. Исследователями предложены следующие
классы методов решения этой задачи:
\begin{enumerate}
\item разработка генераторов тестовых программ вручную (не путать с
разработкой тестовых программ вручную);
\item комбинаторные методы;
\item использование методов генерации входных векторов (ATPG~\cite{ATPGbook});
\item использование методов разрешения ограничений.
\end{enumerate}

